import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-05-14
 * Time: 21:26
 */

/**
 * 队列实现栈
 */
class MyStack {

    Queue<Integer> que1;
    Queue<Integer> que2;


    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new  LinkedList<>();
    }

    public void push(int x) {

        if(!(que1.isEmpty())) {
            que1.offer(x);
        }else if(!que2.isEmpty()){
            que2.offer(x);
        }else {
            que1.offer(x);
        }
    }

    public int pop() {
        if(empty()){
            return -1;
        }

        if(!que1.isEmpty()) {
            int size = que1.size();
            for(int i = 0;i < size-1;i++) {
                que2.offer(que1.poll());
            }

            return que1.poll();

        }else {

            int size = que2.size();
            for(int i = 0;i < size-1;i++) {
                que1.offer(que2.poll());
            }

            return que2.poll();
        }
    }

    public int top() {
        if(empty()){
            return -1;
        }
        if(!que1.isEmpty()) {
            int size = que1.size();
            for(int i = 0;i < size-1;i++) {
                que2.offer(que1.poll());
            }

            int ret = que1.peek();
            que2.offer(que1.poll());
            return ret;

        }else {

            int size = que2.size();
            for(int i = 0;i < size-1;i++) {
                que1.offer(que2.poll());
            }

            int ret = que2.peek();
            que1.offer(que2.poll());
            return ret;
        }
    }

    public boolean empty() {
        return que1.isEmpty()&&que2.isEmpty();
    }
}

/**
 * 栈实现队列
 */
class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 =  new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);

    }

    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!stack2.isEmpty()) {
            return stack2.pop();
        }else {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    public int peek() {
        if(empty()) {
            return -1;
        }
        if(!stack2.isEmpty()) {
            return stack2.peek();
        }else {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}
class MinStack {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MinStack() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int val) {
        s1.push(val);
        if(s2.isEmpty()) {
            s2.push(val);
        } else {
            int x = s2.peek();
            if(val <= x) {
                s2.push(val);
            }
        }
    }

    public void pop() {
        int x = s1.peek();
        int y = s2.peek();
        if(x==y) {
            s1.pop();
            s2.pop();
        }else {
            s1.pop();
        }

    }

    public int top() {
        return s1.peek();
    }

    public int getMin() {
        return s2.peek();
    }
}

public class Main {

}
